package Test;


import java.util.Arrays;

/**
 * @author Kevin
 * @date 2020/2/28 17:24
 */
public class Sorts1 {
    //冒泡排序
    public static void BubbleSort(int[] nums) {
        int n = nums.length;
        if (n == 1) return ;

        for(int i = 0; i < n; i++) {
            boolean flag = false;
            for(int j = 0; j < n-i-1; j++) {
                if (nums[j] < nums[j+1]) {
                    int temp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                    flag = true;
                }
            }
            if (!flag) return;//说明已经有序，不再冒泡
        }
    }
    //选择排序
    public static void SelectionSort(int nums[]) {
        int n = nums.length;
        if (n == 1) return;

        int maxIds;


        for(int i = 0; i < n-1; i++) {
            maxIds = i;
            for(int j = i+1; j < n; j++) {
                if (nums[j] >nums[maxIds]) {
                    maxIds = j;
                }
            }
            if (maxIds != i) {
                int temp = nums[maxIds];
                nums[maxIds] = nums[i];
                nums[i] = nums[maxIds];
            }
        }
    }

    //插入排序
    public static void insertSort(int[] nums) {
        int n = nums.length;
        if(n == 1) return;
        int i,j;

        for(i = 1; i < n; i++) {
            int val = nums[i];
            for (j = i-1; j >= 0; j--) {
                if (val > nums[j]) {
                    nums[j+1] = nums[j];
                } else {
                    break;
                }
            }
            nums[j+1] = val;
        }
    }
    //希尔排序
    public static void shellSort(int[] arr) {
        int len = arr.length;
        if (len == 1) return;

        //进行分组，最开始的增量（gap）为数组长度的一半
        for(int gap = len/2; gap >0; gap /= 2) {
            //对各个分组进行排序插入
            for(int i = gap; i < len; i++) {
                //将arr[i]插入到所在分组的正确位置
                insertI(arr, gap, i);
            }
        }

    }
    private static void insertI(int[] arr, int gap, int i) {
        int inserted = arr[i];
        int j;
        //插入的时候按组进行插入（组内元素两两相隔gap）
        for (j = i - gap; j >= 0; j -= gap) {
            if (inserted < arr[j]) {
                arr[j + gap] = arr[j];
            } else {
                break;
            }
            arr[j+gap] = inserted;
        }
    }

    //归并排序
    public static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;

        int q = (left + right) / 2;
        mergeSort(nums, left, q);
        mergeSort(nums, q+1, right);
        merge(nums, left, q, right);
    }
    public static void merge(int[] nums, int left, int q, int right){
        int i = left;
        int j = q + 1;
        int[] temp = new int[right - left + 1];
        int t = 0;

        while(i<=q && j <= right) {
            if (nums[i] <=  nums[j]) {
                temp[t++] = nums[i++];
            } else {
                temp[t++] = nums[j++];
            }
        }
        //还有剩余
        int start = i;
        int end = q;
        if (j <= right) {
            start = j;
            end = right;
        }

        while(start <= end) {
            temp[t++] = nums[start++];
        }
        //拷贝回原数组
        for (int l = 0; l <= right - left; l++) {
            nums[l + left] = temp[l];
        }
    }

    //快速排序
    public static void quickSort(int[] nums, int left, int right) {
        if (left >= right) return;

        int q = partition(nums, left, right);
        quickSort(nums, left, q-1);
        quickSort(nums, q+1, right);
    }
    public static int partition(int[] nums, int left, int right) {
        int val = nums[right];
        int i = left;
        for (int j = left; j <right; j++) {
            if (nums[j] > val) {
                if (i == j) {//如果是第一个
                    i++;
                } else {//保证在i之前的比val大,交换i和j
                    int temp =nums[j];
                    nums[j] = nums[i];
                    nums[i++] = temp;
                }
            }
        }
        //最后交换right处的val和位置i
        int temp = nums[right];
        nums[right] = nums[i];
        nums[i] = temp;
        return i;
    }

    //找出nums中的topK
    public static int findTopK(int[] nums, int left, int right, int k) {
        if (left >= right) return 0;

        int q = partition(nums, left, right);
        if (q+1 == k) return nums[q];
        else if (q+1 < k) return findTopK(nums,q+1, right, k);
        else return findTopK(nums, left, q-1, k);

    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 6, 8, 4, 12, 11, 13, 15, 7, 9, 0, -1};
//        bubbleSort(arr);
//        bubbleSort2(arr);
//        selectSort(arr);
//        mergeSort(arr, 0, arr.length - 1);
        quickSort(arr, 0, arr.length - 1);

//        Arrays.sort(arr);
        print(arr);
    }

    public static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

}
